package 刷题;
//杨辉三角

import com.sun.deploy.net.MessageHeader;

import java.util.ArrayList;
import java.util.List;

/**
 * 1.将杨辉三角和列对其，从第三行骑中间元素都等于前一行元素对应位置的值和对应位置前一个值的和
 * 2.每一行头和尾都是1
 * 3.每一行的元素个数等于行数
 */
public class Solution118 {
    public List<List<Integer>> generate(int numRows){
        //外层的List
        List<List<Integer>> outList = new ArrayList<List<Integer>>();
        //第一行
        List<Integer> inList = new ArrayList<>();
        inList.add(1);
        //第一行顺序表添加到最外层顺序表
        outList.add(inList);
        for (int i = 1; i < numRows; i++) {
            //当前行顺序表
            List<Integer> curList = new ArrayList<>();
            //前一行顺序表
            List<Integer> preList = outList.get(i-1);
            //每行的第一个数都是1
            curList.add(1);
            for (int j = 1; j < i; j++) {
                //由于当前行元素等于上一行j和j-1元素之和，因此前面要记录前一行顺序表
                curList.add(preList.get(j) + preList.get(j - 1));
            }
            //每一行得最后一个元素也为1
            curList.add(1);
            //将当前行添加至最外层顺序表中
            outList.add(curList);
        }
        return outList;
    }
}
